import collections

cimport cython
cimport libc.stdlib #malloc, free

from ..common import (
 TAG_NOUN, TAG_PRONOUN,
 TAG_VERB, TAG_VERB_TRANSITIVE, TAG_VERB_INTRANSITIVE,
 TAG_ADJECTIVE, TAG_ADVERB,
 TAG_PREPOSITION,
 TAG_INTERJECTION,
 TAG_CONJUNCTION,
)

Word = collections.namedtuple("Word", ("token", "part_of_speech"))

cdef class _Node:
    cdef list _successors
    cdef char * 
    cdef ushort _value
    
    cdef __init__(self):
        self._successors = []
        self._value = 0
        
    cdef void _digest(self, str token, ushort part_of_speech):
        if len(token) == 0:
            self._value |= part_of_speech
            return
            
        cdef Node* next_node
        for (next, node) in self._successors:
            if next == token[0]:
                next_node = node
                break
        else:
            next_node = Node()
            self._successors.append((token[0], next_node))
            
        next_node._digest(token[1:], part_of_speech)
        
    cdef void _optimise(self):
        #This is mostly a sort so that search time in each node can be log(n),
        #but it also moves entries from lists to arrays
        if self._successors:
            for (_, node) in self._successors:
                node._optimise()
            self._successors.sort()
            #TODO: Generate two arrays of length equal to successors, one with pointers to
            #Node instances (to handle the tree) and one with chars, to map the leaves to paths.
        #No need to waste memory: free the list
        self._successors = NULL
        
        #The pointer the list occupied could be used to hold a pointer to a PyUnicode string
        #containing the intermediary characters until the next point with a split or a value,
        #to collapse long paths like "antidi[sestablishmentarianisn]"
        
    cdef ushort _resolve(self, str token):
        if len(token) == 0:
            return self._value
            
        #Do a bisect-search
        #If a path is found, recurse into it and return the result
        
        return 0 #No path exists, so it's not a word
        
cdef class Processor(_Node):
    def __init__(self, unicode path):
        """
        Turns a dictionary of words in a language, tagged with part-of-speech
        markup, into a high-performance in-memory database.
        
        @param str path: The path of the dictionary to be processed.
        """
        _Node.__init__(self)
        
        dictionary = open(path, 'rb')
        i = 0
        try:
            for (i, line) in enumerate(dictionary):
                (word, part_of_speech) = line.strip().split(',')
                self._digest(word, self._encode_part_of_speech(part_of_speech))
        except Exception as e:
            raise ValueError("{path}:{i}:"{line}": {error}".format(
             path=path,
             i=i,
             line=line,
             error=e,
            ))
        else:
            self._finalise()
        finally:
            dictionary.close()
            
    cdef ushort _encode_part_of_speech(self, str part_of_speech):
        """
        Parses a character-string of part-of-speech elements and generates a
        compact encoding.
        
        @param str part_of_speech: The elements to be processed.
        @return int: A compact encoding of part-of-speech elements.
        """
        cdef ushort encoding = 0b1000000000000000
        for c in part_of_speech:
            if c == 'N':
                encoding |= TAG_NOUN
            elif c == 'V':
                encoding |= TAG_VERB
            elif c == 't':
                encoding |= TAG_VERB_TRANSITIVE
            elif c == 'i':
                encoding |= TAG_VERB_INTRANSITIVE
            elif c == 'A':
                encoding |= TAG_ADJECTIVE
            elif c == 'v':
                encoding |= TAG_ADVERB
            elif c == 'C':
                encoding |= TAG_CONJUNCTION
            elif c == 'P':
                encoding |= TAG_PREPOSITION
            elif c == '!':
                encoding |= TAG_INTERJECTION
            elif c == 'r':
                encoding |= TAG_PRONOUN
        return encoding
        
    cdef void _finalise() except *:
        """
        Applies optimisations and prepares the processor for use.
        """
        self._optimise()
        
    def tuple query(self, unicode line):
        """
        @param str line: The string to be evaluated.
        @return list: The density of the current language and a list of
                      `Word`s, derived from the internal parsing rules.
        """
        cdef list words = self._query(line)
        return (float(sum(1 for w in words if w.part_of_speech)) / len(words), words)
        
    cdef list _query(self, unicode line):
        """
        @param str line: The string to be evaluated.
        @return list: A list of tokens extracted from `line`, with None
                      representing unknown elements, and the others being
                      tuples of the token and its corresponding part-of-speech.
        """
        raise NotImplementedError("_query() must be implemented in subclasses")
        